package me.sealer.algorithm.sort;

/**
 * Created by sealer on 17/03/02.
 */
public class Shell {
    public static void sort(int[] data) {
        // 计算出最大的h值
        int h = 1;
        while (h <= data.length / 3) {
            h = h * 3 + 1;
        }
        while (h > 0) {
            for (int m = 0; m < h; m++) {//h组都要进行插入排序， 内部循环为一组数据的插入排序
                for (int i = m + h; i < data.length; i += h) {
                    if (data[i] < data[i - h]) {
                        int tmp = data[i];
                        int j = i - h;
                        while (j >= 0 && data[j] > tmp) {
                            data[j + h] = data[j];
                            j -= h;
                        }
                        data[j + h] = tmp;
                    }
                }
            }
            // 计算出下一个h值
            h = (h - 1) / 3;
        }
    }
}
